package 剑指offer_leetcode;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * JZ49丑数
 */
public class 剑指Offer49_丑数 {
    public int nthUglyNumber(int n) {
        if(n==0)
            return 0;
        int[] factors = {2, 3, 5};
        HashMap<Long, Integer> mp = new HashMap<>();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        mp.put(1L, 1);
        pq.offer(1L);
        long res = 0;
        for(int i=0;i<n;i++){
            res = pq.poll();
            for(int j = 0; j < 3; j++){
                long next = (long)res * factors[j];
                if(!mp.containsKey(next)){
                    mp.put(next, 1);
                    pq.offer(next);
                }
            }
        }
        return (int) res;
    }
}
